package binarySearch;

/**
 * 给定如下数组{7,8,9,1,2,3,4,6}(元素不重复)
 * 查找某个元素是否存在。如果存在，打印下标。不存在，返回-1
 * 时间复杂度尽可能小。
 * 33. 搜索旋转排序数组
 */
public class Solution2 {

    public static void main(String[] args) {
        int[] arr=new int[]{7,8,9,1,2,3,4,6};
        System.out.println(new Solution2().search(arr,2));
    }

    public int search(int[] arr,int n){
        int lastValue=arr[arr.length-1];
        int start=0;
        int end=arr.length-1;
        while (start<=end){
            if (n==arr[start]){
                return start;
            }
            if (n==arr[end]){
                return end;
            }
            int mid=start+(end-start)/2;
            if (n==arr[mid]){
                return mid;
            }else {
                if (arr[mid]>lastValue){ //当中位数在大数组
                    if (n>arr[mid]){ //比大数组的某元素大的，只能在temp的右边
                        start=mid+1;
                    }else { //比大数组的某元素小的，可能在大数组左边，也可能在小数组里
                        if (n>lastValue){
                            end=mid-1;
                        }else { //在小数组里
                            start=mid+1;
                        }
                    }
                }else { //当中位数在小数组里
                    if (n<arr[mid]){ //比小数组的某元素还小的值，只能在小数组temp左边
                        end=mid-1;
                    }else {
                        if (n>lastValue){ //在大数组里end移动
                            end=mid-1;
                        }else { //在小数组里右边
                            start=mid+1;
                        }
                    }
                }
            }
        }
        return -1; //找不到
    }
}
